Abstract: Optimal scheduling to minimize mean response time is well understood for a single-server queue. However much less is known for multi-server queueing systems. In the worst-case adversarial setting, it is impossible to get anywhere near optimal scheduling and load balancing for multi-server queueing systems. In this talk we instead approach optimality from the perspective of the stochastic setting where job sizes and arrivals are drawn from general distributions. In the stochastic setting, we derive the first optimal scheduling policies for the two most common multi-server architectures.

This was an invited talk at STOC 2021's TheoryFest. The talk is based on two papers, both of which won Best Student Paper Awards: one at IFIP Performance 2018, and the other at ACM SIGMETRICS 2019. Both papers are joint with PhD students, Isaac Grosof and Ziv Scully.